/*
*   给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。
* 你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。

* 示例:
* 给定 nums = [2, 7, 11, 15], target = 9
* 因为 nums[0] + nums[1] = 2 + 7 = 9
* 所以返回 [0, 1]
*
*/

#include <vector>
#include <algorithm>
#include <iostream>
#include <map>


using std::vector;

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target);
};

#if 0
/*  时间换空间
*   执行用时：
732 ms
, 在所有 C++ 提交中击败了
23.27%
的用户
内存消耗：
7.1 MB
, 在所有 C++ 提交中击败了
100.00%
的用户
*/
vector<int> Solution::twoSum(vector<int>& nums, int target)
{
    for (auto i=0u; i<nums.size()-1; ++i)
    {
        auto iter = find(nums.cbegin()+i+1, nums.cend(), target - nums[i]);
        if (nums.cend() != iter)
        {
            return vector<int>({static_cast<int>(i), static_cast<int>(iter - nums.cbegin())});
        }
    }
    return vector<int>();
}

#else
/* 空间换时间
*/
vector<int> Solution::twoSum(vector<int>& nums, int target)
{
    std::map<int, int> valIndexMap;
    auto loop = nums.size();
    for (auto i=0u; i<loop; ++i)
    {
        auto iter = valIndexMap.find(target - nums[i]);
        if (iter != valIndexMap.end())
        {
            return vector<int>({iter->second, static_cast<int>(i)});
        }
        valIndexMap[nums[i]] = static_cast<int>(i);
    }
    return vector<int>();
}
#endif


int main()
{
    vector<int> nums = {3,2,4};

    Solution obj;
    auto ret = obj.twoSum(nums, 6);

    if (2 == ret.size())
    {
        std::cout << ret.at(0) << " " << ret.at(1) << std::endl;
    }
    return 0;
}